重学图结构 |
您所在的位置：网站首页 › 数据结构ve vl › 重学图结构 |
重学图结构
|
图
图的描述
G = (V, E)，一个偶对V：顶点（数据元素）组成的有穷非空集合{E}：边的有穷集合、图的逻辑结构：多对多
相关术语
无向图：每条边都是无方向的，如下图1 有向图：每条边都是有方向的，如下图2 完全图：任意两个顶点都有边相连，分为无向完全图、有向完全图，如下图3、4 稀疏图：有很少边或者弧的图(e < n * log(2, n)) 弧：带有方向的边也叫弧 稠密图：有较多的边或者弧的图 网：边或者弧带有权值的图 邻接：两个顶点被边或者弧相连称为邻接，无向图中使用(vi, vj)表示vi与vj互为邻接点；有向图中使用，表示vi邻接到vj，vj邻接于vi 关联（依附）：边或者弧与顶点之间的关系，说白了就是这条边或者弧就是某两个顶点连一起得到的，这个关系就是关联 顶点的度：与顶点关联的边的数目；在有向图中，顶点的度等于顶点的出度和入度之和 入度：以当前顶点为终点的有向边的条数，图二中A的入度为2 出度：以当前顶点为起点的有向边的条数，图二中A的出度为1 有向树：仅有一个顶点入度为0，其余顶点的入度为1的有向图被称为有向树 路径：接续的边（不间断的边边相连）构成的顶点序列 路径长度：网的某路径的权值之和 回路（环）：第一个顶点和最后一个顶点具有相同的路径 简单路径：除了起点和终点是一样的，其他顶点均不同的路径 简单回路（简单环）：除了路径的起点和终点一样外，其余的顶点均不相同的路径 连通图（强连通图）：在无（有）向图G = (V, {E})中，若对任何两个顶点v、都存在从v到u的路径，则称G是连通图，图2就不是强连通图，因为A到D有路径，但是不存在D到A的路径 权：就是网的边上的权值 子图：G = (V, {E})，G1 = (V1, {E1})，若V1∈V，E1∈E，则称G1是G的子图 连通分量（强连通分量）：无向图G的极大连通子图称为G的连通分量 极大连通子图：该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不在连通 强连通分量：有向图G的极大连通子图称为G的强连通分量 极大强连通子图：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不在是强连通 极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边就不再连通 生成树：包含无向图G所有顶点的极小连通子图 生成森林：对非连通图，由各个连通分量的生成树的集合 图的重要操作 创建图 CreateGraph(&G, V, VR) 初始条件：V是图的顶点集，VR是图中弧的集合 操作结果：按V和VR的定义构造图G DFS（深度优先遍历） DFSTraverse(G) 初始条件：图存在 操作结果：对图进行深度优先遍历 BFS（广度优先遍历） BFSTraverse(G) 初始条件：图G存在 操作结果：对图进行广度优先遍历 图的存储结构 借助二维数组表示，称为数组表示法（邻接矩阵）链式存储结构：使用多重链表（如邻接表、连接多重表、十字链表） 无向图的邻接矩阵表示法 建立一个顶点表（记录顶点信息）和一个邻接矩阵（顶点之间的关系）用一维数组表示顶点表邻接矩阵用二维数组，用1表示两点之间有边或者弧；用0表示两点之间不存在有边或者弧；默认顶点与自身为0
上图的邻接矩阵为 ABCDEA01010B10101C01001D10001E01110 无向图的邻接矩阵是一个对称矩阵顶点i的度是第i行或者列的1的个数 有向图的邻接矩阵表示法 vi到vj的弧记录为1，不存在的话记录0
上图的邻接矩阵为 ABCDA0101B0000C1000D0010 网的邻接矩阵表示法如果两点之间存在边或者弧（因为网也分为有向网和无向网），则记录值，否则记录一个特殊数，比如说0，-1 上图的邻接矩阵为 V1V2V3V4V5V6V1050700V2004000V3800009V4005006V5000500V6300010 代码实现邻接矩阵表示法 // 邻接矩阵存储法的思想是基于两个数组分别存储顶点（一维）和邻接矩阵（二维） typedef char VertexType; // 顶点类型 typedef int ArcType; // 边的权值的类型 #define MAXSIZE 10 // 最大顶点数目 typedef struct { VertexType vertex[MAXSIZE]; ArcType arcs[MAXSIZE][MAXSIZE]; // 记录当前顶点数、边数 int vernum, arcnum; } AMGraph; 实现无向网的表示 输入顶点数和边数把顶点添加到顶点表初始化邻接矩阵，默认权值全是0值（就是你设定的不存在的值）构造邻接矩阵 使用邻接矩阵的优缺点 优点 直观、简单、好理解方便检查任意对顶点是否存在关联便于计算顶点的度 缺点 不便于删除和增加新顶点边太少时，仍是一个是一个nxn（n是顶点个数）稀疏矩阵，浪费空间统计稀疏图边数浪费时间 相关代码 // 用于表示存在关联的两个顶点以权值 typedef struct { VertexType vertex1; VertexType vertex2; ArcType weight; } Linked; // 辅助函数，用于获取顶点在顶点集的索引 int getIndex(AMGraph *graph, VertexType name); // 建立无向网 // 参数依次是边的顶点个数、边的个数、网、顶点集、关联数组集 void create(int _vernum, int _arcnum, AMGraph *graph, VertexType vertexes[_vernum], Linked linked[_arcnum]); // 直观的打印出邻接矩阵 void printMatrix(AMGraph *graph); // // Created by 20281 on 2023/6/11. // #include "AdjacencyMatrix.h" #include "stdio.h" int getIndex(AMGraph *graph, VertexType name){ for (int i=0;ivernum;i++){ if (graph->vertex[i] == name) return i; else continue; } return -1; } void create(int _vernum, int _arcnum, AMGraph *graph, VertexType vertexes[_vernum], Linked linked[_arcnum]){ graph->vernum = _vernum; graph->arcnum = _arcnum; for (int i=0;i for (int j=0;j int ver1 = getIndex(graph, linked[i].vertex1); int ver2 = getIndex(graph, linked[i].vertex2); ArcType weight = linked[i].weight; graph->arcs[ver1][ver2] = weight; graph->arcs[ver2][ver1] = weight; } } void printMatrix(AMGraph *graph){ printf("\t"); for (int i=0;ivernum;i++){ printf("%c\t", graph->vertex[i]); } printf("\n"); for (int i=0;ivernum;i++){ printf("%c\t", graph->vertex[i]); for (int j=0;jvernum;j++){ printf("%d\t", graph->arcs[i][j]); } printf("\n"); } }
对上面网的测试 // // Created by 20281 on 2023/6/11. // #include "AdjacencyMatrix.h" int main(){ // 创建img8中的网 Linked linkeds[6] = { {'A', 'B', 4}, {'A', 'D', 6}, {'B', 'C', 3}, {'B', 'F', 10}, {'C', 'E', 7}, {'D', 'E', 11}, }; VertexType vertexes[6] = {'A', 'B', 'C', 'D', 'E', 'F'}; AMGraph amGraph; create(6, 6, &amGraph, vertexes, linkeds); // 打印 printMatrix(&amGraph); return 0; }输出结果 A B C D E F A 0 4 0 6 0 0 B 4 0 3 0 0 10 C 0 3 0 0 7 0 D 6 0 0 0 11 0 E 0 0 7 11 0 0 F 0 10 0 0 0 0 邻接表存储法 由顶点构成的结点组成的一维数组用线性链表存储关联同一顶点的边（或者以顶点为尾的弧）直观展示无向图的邻接表存储法，空间复杂度O(n+2e)，其中n是顶点数，e是边数，下同 直观展示有向图的出度邻接表存储法，空间复杂度O(n+e)
对上面网的测试 // 邻接表 ALGraph alGraph; Linked2 linkeds_2[6] = { {'A', 'B', 4}, {'A', 'D', 6}, {'B', 'C', 3}, {'B', 'F', 10}, {'C', 'E', 7}, {'D', 'E', 11}, }; ALGraph alGraph2; Linked2 linkeds_3[6] = { {'A', 'B', 4}, {'A', 'D', 6}, {'B', 'C', 3}, {'B', 'F', 10}, {'C', 'E', 7}, {'D', 'E', 11}, }; createALG1( &alGraph, 6, 6, vertexes, linkeds_2); createALG2( &alGraph2, 6, 6, vertexes, linkeds_3); // 直观打印 printLinkedList(&alGraph); printLinkedList(&alGraph2); // 释放链表内存 freeLinkedList(&alGraph); freeLinkedList(&alGraph2);输出结果 A-->(6, 3)-->(4, 1)--> B-->(10, 5)-->(3, 2)-->(4, 0)--> C-->(7, 4)-->(3, 1)--> D-->(11, 4)-->(6, 0)--> E-->(11, 3)-->(7, 2)--> F-->(10, 1)--> A-->(4, 1)-->(6, 3)--> B-->(4, 0)-->(3, 2)-->(10, 5)--> C-->(3, 1)-->(7, 4)--> D-->(6, 0)-->(11, 4)--> E-->(7, 2)-->(11, 3)--> F-->(10, 1)--> 邻接表改进 对于有向图，缺点是求取顶点的度困难，需要由出度表和入度表结合才行，于是有了十字链表对于无向图，缺点是每条边都需要存储两边，于是有了邻接多重表，邻接多重表的出现是为了解决一条边存储一次且能够表示两个点的问题 图（网）的遍历 把连通图的每个顶点遍历一遍，且每个顶点仅被遍历一次设置辅助数组记录每个顶点是否被访问过，对应顶点初始状态为0，访问则记录为1核心是根据当前顶点找到并遍历与之相邻的顶点 深度优先搜索遍历（DFS）（来自大佬的总结）最直观的例子就是“走迷宫”。假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口（这个出口可以理解为最后一个被遍历的顶点）。这种走法就是一种深度优先搜索策略。 广度优先搜索遍历（BFS）（来自大佬的总结） 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。 基于无向图的邻接矩阵表示法实现对图的DFS // DFS算法的实现 // index是开始起点的索引、visited是辅助数组、_c是计数器，我特地设定的，用于统计递归了多少次 void _DFS(AMGraph *graph, int index, int visited[], int *_c); void DFS(AMGraph *graph, int index); void _DFS(AMGraph *graph, int index, int visited[], int *_c){ *_c += 1; printf("%c", graph->vertex[index]); visited[index] = 1; for (int i=0;ivernum;i++){ // 当前的顶点与邻近的顶点之间有关联并且邻近顶点未被访问情况下 if (graph->arcs[index][i] != 0 && visited[i] == 0){ _DFS(graph, i, visited, _c); } } } // _DFS才是核心，DFS只是辅助作用和直观打印过程 void DFS(AMGraph *graph, int index){ // 辅助数组，用于记录每个点是否被访问 int visitedArray[graph->vernum]; for (int i = 0;ivernum;i++){ visitedArray[i] = 0; } int _c = 0; printf("开始遍历……\n"); _DFS(graph, index, visitedArray, &_c); printf("\n"); printf("函数触发了%d次……\n", _c); } // 对img11进行DFS // 用1表示边边关联，而不是权重 Linked linked_img11[6] = { {'1', '2', 1}, {'1', '3', 1}, {'1', '4', 1}, {'2', '5', 1}, {'3', '5', 1}, {'4', '6', 1} }; VertexType vertexes_img11[6] = {'1', '2', '3', '4', '5', '6'}; AMGraph amGraph_img11; create(6, 6, &amGraph_img11, vertexes_img11, linked_img11); printMatrix(&amGraph_img11); // DFS DFS(&amGraph_img11, 1); // 结果 // 开始遍历…… // 213546 // 函数触发了6次…… 基于邻接链表的无向图的代码实现BFS // BFS算法的实现 // index 表示从哪个顶点作为开始访问 void _BFS(ALGraph *graph, int index, int vertexArray[], Queue *queue); void BFS(ALGraph *graph, int index); void _BFS(ALGraph *graph, int index, int vertexArray[], Queue *queue){ push(queue, index); printf("%c ", graph->vertexes[index].vert); vertexArray[index] = 1; while (isEmpty(queue) != 1){ int outIndex = pop(queue); // 找到与出队顶点相关的且没被访问的顶点 ArcNode * currentNode = graph->vertexes[outIndex].firstArc; // 找到相关点 while (currentNode != NULL){ // 找到没被访问的点 if (vertexArray[currentNode->index] == 0){ push(queue, currentNode->index); printf("%c ", graph->vertexes[currentNode->index].vert); vertexArray[currentNode->index] = 1; } else {} currentNode = currentNode->next; } } } void BFS(ALGraph *graph, int index){ int vertexArray[graph->vernum]; for (int i=0;ivernum;i++){ vertexArray[i] = 0; } printf("Begin Traversal ......\n"); Queue queue; createQueue(&queue); _BFS(graph, index, vertexArray, &queue); printf("\n"); } // 对img12实现邻接链表的BFS演示 Linked2 linked_img12[9] = { {'1', '2', 1}, {'1', '3', 1}, {'2', '4', 1}, {'2', '5', 1}, {'3', '6', 1}, {'3', '6', 1}, {'4', '8', 1}, {'5', '8', 1}, {'6', '7', 1}, }; VertexType img12_vec[8] = {'1', '2', '3', '4', '5', '6', '7', '8'}; ALGraph alGraph_img12; createALG2(&alGraph_img12, 8, 9, img12_vec, linked_img12); printLinkedList(&alGraph_img12); BFS(&alGraph_img12, 2); // 释放内存 freeLinkedList(&alGraph_img12); 1-->(1, 1)-->(1, 2)--> 2-->(1, 0)-->(1, 3)-->(1, 4)--> 3-->(1, 0)-->(1, 5)-->(1, 5)--> 4-->(1, 1)-->(1, 7)--> 5-->(1, 1)-->(1, 7)--> 6-->(1, 2)-->(1, 2)-->(1, 6)--> 7-->(1, 5)--> 8-->(1, 3)-->(1, 4)--> Begin Traversal ...... 3 1 6 2 7 4 5 8 图的应用 最小生成树最短路径拓扑排序关键路径 最小生成树 生成树：所有顶点连在一起，但是不存在回路的图。它顶点个数与图顶点个数一样，是图的极小连通子图，去掉任意一条边就不再连通。n个顶点的生成树有n-1条边最小生成树：一个无向网可以有多个不同的生成树，各边权值和最小的无向网被称为最小生成树（最小代价生成树）MST性质：设N = (V, E)是一个连通网，U是顶点集V的一个非空子集。若边(u, v)是一条具有最小权值的边，其中u∈U，v∈V-U（差集的意思），则必存在一颗包含边(u, v)的最小生成树根据MST性质，n个顶点分为两个集合——已落在生成树上的顶点集：U，尚未落在生成树上面的顶点集：V-U，然后在连通的U中的顶点和V-U顶点组成的边选取权值最小的边相关算法：Prim算法、Kruskal算法 Prim算法（普利姆算法） 设N = (V, E)是连通网，TE是N上最小生成树中边的集合初始令U = {u。}(u。∈V)，TE = {}在所有u∈U，v∈V-U的边(u, v)∈E中，找一条权值最小的边将(u。, v，)并入集合TE中，同时v。加入U中重复第三第四步，直到U = V为止，最终得到T = (V, TE)是N的最小生成树下面大致写一份代码实现，基于邻接链表 ALGraph Prim(AlGraph *graph){ ALGraph mst; // 初始 U = {mst.vertexes[0].vert}; V_U = {除了mst.vertexes[0].vert外的所有的点}; // 这里面TE就是Linked2类型的 Linked2 links[graph->vernum - 1]; // links当前添加元素的计数 _counter = 0; // 直到U = V为止，也就是说U长度为V为止 while(getLength(U) != graph->vernum){ // 在所有u∈U，v∈V-U的边(u, v)∈E中，找一条权值最小的边 // 将(u。, v，)并入集合TE中，同时v。加入U中 link = {}; link.weight = 0; for (u in U){ for (v in V_U){ // 如果两点成关联 if (islinked(u, v)){ // 每次都比较，获取最小权值的关联 if (getWeight(u, v) ALGraph mst; // 初始化只有独立的顶点，没有关联的网 createALG2(&mst, graph->vernum, 0, graph->vertexes, NULL); // 获取graph的有关联的边点，得到Linked2 links getLinks(graph); // 先从links找到权值最小边mlink添加到mst，并从links删除此组合 getMinCompose(links); remove(&links, mlink); append(&mst, mlink); // 计数，成功了graph->vernum-2次停止 _counter = 1; while (_counter vernum-2){ // 从links找到权值最小且不形成的link添加到mst，并删除这样的link // 那如果这个边权值最小，但形成闭环，是不是要从考虑的边中删除 getMinCompose(links); // 设为temp_link; // 形成闭环 if (isLoop(mst, temp_link)){} else{ append(&mst, temp_link); _counter++; } remove(&links, temp_link); } return mst; } 对比 算法名字Prim算法Kruskal算法算法思想选择点选择边时间复杂度O(n^2)O(ElogE)适用范围稠密网稀疏网 最短路径 在有线网顶点A到顶点B的路径中找到各边权值和最小的两类问题：两点之间的最短路径（单源最短路径）、从某起点出发到其他各点最短路径（所有顶点间的最短路径）针对上面两个问题的不同经典的算法：Dijkstra算法（迪杰斯特拉算法）、Floyd算法（弗洛伊德算法） Dijkstra算法 先找到从起点v。到各终点vk的直达路径（就是两个点之间有关联的），然后从中找到最短的然后对其余各路径进行适当调整
对上图进行算法分析 备注 使用0表示此处无路径（很多教程或者视频使用无穷大）使用‘-’符号表示此处此点已经找到最短路径 点名从v0到各点的最短路径v1131313---v28-----v3013----v430301919--v5000222121v63232322020-当前最短点v2v3v1v4v6v5路径长度81313192021 Floyd算法 解决顶点间的最短路径逐个增加中间顶点试探从vi到vj的所有可能存在的路径中，选出一条长度最短的路径 有向无环图（DGA图） 顾名思义，有向图中不存在环（没有回路存在）
该图中左图就是一个有向无环图，右侧不是 分为AOV网和AOE网AOV网：用一个有向图表示一个工程中的各个子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，这种有向图称为顶点表示活动的网，简称AOV网。用于解决拓扑排序问题AOE网：用一个有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或者结束事件，称这种有向图为边表示活动的网，简称AOE网。用于解决关键路径问题 AOV网 若从顶点i到顶点j有一条有向路径，则i是j的前驱，j是i的后继若是网中有向边，则i是j的直接前驱，j是i的直接后继AOV网中不允许有回路 拓扑排序 在AOV网中没有回路前提下，把全部活动排成线性序列，如果存在弧，则在这个序列中，i一定排在j前面，具有这样性质的线性序列被称为拓扑有序序列，相应的排序算法被称为拓扑排序。是用来解决任务之间的前后依赖关系的，比如说，大学课程中，必须学完高等数学，才是开设基于高等数学知识的大学物理这门课程拓扑排序把一个网变成了一个线性序列拓扑序列不唯一拓扑排序可以用来检测有向网中存在环——如果输出的有序序列包含全部顶点，则说明没有环，否则存在 具体实现 在有向图中选择一个没有前驱的顶点并且输出从图中删除该顶点以及所有以它为尾的弧重复上面的两步，直到全部的顶点都被输出；或者是图中不存在无前驱的顶点为止 AOE网 顶点表示事件、弧表示活动、弧的权表示活动持续时间出度为0的顶点为汇点、入度为0的顶点为源点 关键路径 从源点到汇点路径长度最长的路径 具体实现 ve(vj)：表示事件vj最早的发生时间vl(vj)：表示事件vj最晚的发生时间e(i)：表示活动ai的最早开始时间l(i)：表示活动ai的最晚开始时间l(i) - e(i)：表示完成活动ai的时间余量关键活动：关键路径上的活动，即l(i) == e(i)的活动设活动ai用弧表示，其持续时间记为w(j, k)ve(j) = Max(ve(i) + w(i, j))vl(i) = Min(vl(j) - w(i, j))
对上面AOE网进行关键路径查找 顶点vevlv100v266v346v458v577v6710v71616v81414v91818 活动ell-ea1000a2022a3033a4660a5462a6583a7770a8770a97103a1016160a1114140得到关键活动是：a1 a4 a7 a8 a10 a11 补充 Warshall算法利用Floyd算法求有向图的中心点 Warshall算法 Warshall算法是一种用于解决传递闭包（transitive closure）问题的算法。传递闭包是指在有向图中，如果存在一条路径从节点i到节点j，那么节点i可以达到节点j。Warshall算法的目标是计算出图中所有节点对之间的可达性。 具体而言，Warshall算法通过一个二维矩阵（通常称为邻接矩阵）来表示有向图的连接关系。矩阵中的元素A[i][j]表示从节点i到节点j是否存在一条边。初始时，如果有一条边直接连接节点i和节点j，则A[i][j]为1，否则为0。 Warshall算法的主要思想是通过迭代更新邻接矩阵，以逐步计算出所有节点对之间的可达性。算法的步骤如下： 初始化邻接矩阵，将直接连接的边设置为1，没有直接连接的边设置为0。 对于每个节点k，遍历所有节点对(i, j)，如果存在一条路径从节点i经过节点k到节点j，即A[i][k]为1且A[k][j]为1，则将A[i][j]设置为1。 重复步骤2，直到对每个节点都进行了一次遍历。最终的邻接矩阵将表示图中所有节点对之间的可达性。 通过Warshall算法，最终得到的邻接矩阵能够表明在图中从一个节点到另一个节点是否存在一条路径。如果A[i][j]为1，则表示节点i可以达到节点j；如果A[i][j]为0，则表示节点i无法达到节点j。 总结来说，Warshall算法的实质是通过迭代更新邻接矩阵，来计算出图中所有节点对之间的可达性，从而解决传递闭包问题。 利用Floyd算法求有向图的中心点 图的中心点：图中一个点到其他的顶点的最短路径求和最小思路：在一个带权图G中，求出一个顶点v，使得v到其余顶点的最短路径长度之和最小。首先用弗罗伊德算法求出图中各个顶点之间的最短路径长度，然后再求出每个顶点到其余各顶点的最短路径长度之和，从中选取一个最短路径长度之和最小的顶点即为要求的顶点。声明： 部分图片源于互联网、部分更通俗易懂的概念源于搜索 教学看的是青岛大学王卓老师的 源代码下载：https://gitee.com/PythonnotJava/Data-structure-and-algorithm-collection/tree/master/ReGraph |
【本文地址】